/*
  归并操作
  题目描述
    将 10, 3, 5, 1, 9, 34, 54, 565 这几个数用归并来排序。
  输入
    无
  输出格式
    从小到大排序，用空格隔开。
*/

#include <bits/stdc++.h>

using namespace std;

/*
  函数功能:
    将数组 a 的左半部分 (a[s] ~ a[mid]) 和右半部分 (a[mid + 1] ~ a[e]) 进行合并,
    合并成一个从小到大的有序数组。
    其中, 左半部分(a[s] ~ a[mid])是一个从小到大的有序数组
         右半部分(a[mid + 1] ~ a[e])也是一个从小到大的有序数组
  参数说明:
    a[]  -- 待排序的数组
    b[]  -- 临时数组
     s   -- 对数组 a[] 进行排序的开始下标
     mid -- 对数组 a[] 进行排序的结束下标
     e   -- 对数组 a[] 进行排序的结束下标
*/
void hb(int a[], int b[], int s, int mid, int e) {
    int i = s;       // 左半边部分的开始下标
    int j = mid + 1; // 右半边部分的开始下标
    int k = s;       // 临时数组 b 的开始下标

    /*
      核心思想:
        a[i] 和 a[j] 进行比较，将小的数放到 b[k];
        然后将下标 i或j、k 往后移动 1 位(即+1)
        依次类推, 即可完成将左半部分和右半部分的合并，合并后的数存放在临时数序 b 中!
        最后使用数组 b 中的元素为 数组 a 中的对应元素赋值!
    */
    while (i <= mid && j <= e) {
        if (a[i] <= a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
        }
    }
    while (i <= mid) {
        b[k++] = a[i++];
    }
    while (j <= e) {
        b[k++] = a[j++];
    }
    for (int z = s; z <= e; z++) {
        a[z] = b[z];
    }
}

/*
  函数功能:
    使用归并排序算法, 对数组 a[s] ~ a[e] 按从小到大的顺序进行排序,
    完成排序后, a[s] ~ a[e] 为从小到大的顺序。
  参数说明:
    a[] -- 待排序的数组
    b[] -- 临时数组
     s  -- 对数组 a[] 进行排序的开始下标
     e  -- 对数组 a[] 进行排序的结束下标，其中 e >= s
  小结:
     归并排序使用了递归的方式进行编码实现!
*/
void f(int a[], int b[], int s, int e) {
    // 如果序列中只有 1 个数时，不需要其他排序操作，已经排好序了!
    // 否则就按照如下方式进行递归处理:
    if (s < e) {
        int mid = (s + e) / 2;

        f(a, b, s, mid);     // 对数组 a 的左半部分(a[s] ~ a[mid]), 使用归并排序的方法按从小到大的顺序进行排序
        f(a, b, mid + 1, e); // 对数组 a 的右半部分(a[mid + 1] ~ a[e]), 使用归并排序的方法按从小到大的顺序进行排序
        hb(a, b, s, mid, e); // 将数组 a 的左半部分和右半部进行合并, 合并成一个从小到大的有序数组
    }
}

int main() {
    int a[8] = {10, 3, 5, 1, 9, 34, 54, 565};  // 数组 a, 存放待排序的若干个数, 排序后的数也存放在该数组中
    int b[8];   // 临时数组

    // 使用归并排序算法, 对 a[0] ~ a[7] 按从小到大的顺序进行排序
    f(a, b, 0, 7);

    for (int i = 0; i <= 7; i++) {
        if (i == 7) {
            cout << a[i];
        } else {
            cout << a[i] << " ";
        }
    }

    return 0;
}
